from typing import *
from math import inf

class Solution:

    def minFallingPathSum(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        for i in range(1, m):
            for j in range(n):
                mn = min(matrix[i - 1][j],
                         matrix[i - 1][j - 1] if j > 0 else inf,
                         matrix[i - 1][j + 1] if j < n - 1 else inf)
                matrix[i][j] += mn
 
        return min(matrix[-1])


s = Solution()
print(s.minFallingPathSum([[2, 1, 3], [6, 5, 4], [7, 8, 9]]))
